/*
time:20201028 19:54 PM
key:1.报错内容大概意思为:传入的参数表达式应具有“const myCompare”类型，而你调用的“bool myCompare::operator ()(int,int)”不具备const属性，会丢失const限定，所以无法通过编译。
	故只要将operator()具有const属性便可，如下
user：ldc
*/
#include <math.h>
#include <iostream>
#include<string>
#include <string>
#include<queue>
#include<map>
using namespace std;

class Node
{
public:
	int data;
	Node* rnext;
	Node* lnext;
	Node()
	{
		data = -1;
		rnext = NULL;
		lnext = NULL;
	}
};

struct CmpByKeyLength 
{
	bool operator()(const int& k1, const int& k2) const {
		return k1 < k2;
	}
};
int main()
{
	int range_array[10] = { 0, 9, 1, 8, 2, 7, 3, 6, 4,5 };//乱序数组
	map<int, Node*, CmpByKeyLength > number_to_node;
	Node* head = new Node();
	Node* p1 = head;
	Node* final_node = head;
	int i;
	int n = 10;
	//建立单链表,从第二个节点开始有前驱节点记录。
	for (i = 0; i < n; i++)
	{
		p1->rnext = new Node();
		if (i == n - 1)
		{
			p1->rnext->rnext = head;//最后一个节点的rnext指向头节点
			final_node = p1->rnext;//保留指向最后一个节点的指针
		}
		p1->rnext->lnext = p1;
		p1 = p1->rnext;
	}
	head->lnext = final_node;//让头节点的lnext指向最后一个节点
	//遍历单链表输入数据
	p1 = head;
	for (i = 0; i < n; i++)
	{
		p1->data = range_array[i];
		p1 = p1->rnext;
	}
	//正序遍历
	p1 = head;
	cout << "r正序遍历\n";
	while (p1->rnext != head)
	{
		cout << p1->data;
		p1 = p1->rnext;
	}
	cout << "\n";
	//倒序遍历
	cout << "l倒序遍历,-1为哨兵节点\n";
	p1 = head;
	while (p1->lnext != head)
	{
		cout << p1->data;
		p1 = p1->lnext;
	}
	cout << "\n";
	//正序遍历目的是将数据放入map中，放的同时map已经自动排序了。
	p1 = head;

	while (p1->rnext != head)
	{
		number_to_node.insert(pair<int, Node*>(p1->data, p1));
		p1 = p1->rnext;
	}
	cout << "\n";
	//遍历map，O(n)，逐个修改lnext。
	for (i = 0; i < n; i++)
	{
		
		if (i < n - 1) 
		{
			number_to_node[i]->lnext = number_to_node[i + 1];
		}
		else
		{
			number_to_node[i]->lnext = number_to_node[0];
		}
	
	}
	//二次正序遍历
	p1 = head;
	cout << "二次正序遍历\n";
	while (p1->rnext != head)
	{
		cout << p1->data;
		p1 = p1->rnext;
	}
	cout << "\n";
	//lnext已排序好的二次倒序遍历
	p1 = head;
	cout << "lnext已排序好的二次倒序遍历\n";
	while (p1->lnext != head)
	{
		cout << p1->data;	
		if (p1->data == n - 2)
		{
			cout << p1->lnext->data;
			break;
		}
			p1 = p1->lnext;
	}
	cout << "\n";
}





